package com.darrenchan.leetcode;

import java.util.*;

/**
 * @Desc
 * @Author chenchi03
 * @CreateTime 2019-12-31 10:49
 */
class DirectedGraphNode {
    int label;
    ArrayList<DirectedGraphNode> neighbors;

    DirectedGraphNode(int x) {
        label = x;
        neighbors = new ArrayList<DirectedGraphNode>();
    }
}

public class QLint127 {
    public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
        ArrayList<DirectedGraphNode> res = new ArrayList<>();
        Map<DirectedGraphNode, Integer> nodesIndegree = getNodesIndegree(graph);
        Queue<DirectedGraphNode> queue = new LinkedList<>();
        for (DirectedGraphNode node : nodesIndegree.keySet()) {
            if (nodesIndegree.get(node) == 0) {
                queue.add(node);
            }
        }

        while (!queue.isEmpty()) {
            DirectedGraphNode node = queue.poll();
            res.add(node);
            for (DirectedGraphNode neighbor : node.neighbors) {
                nodesIndegree.put(neighbor, nodesIndegree.get(neighbor) - 1);
                if (nodesIndegree.get(neighbor) == 0) {
                    queue.add(neighbor);
                }
            }
        }
        return res;
    }

    public ArrayList<DirectedGraphNode> topSortDFS(ArrayList<DirectedGraphNode> graph) {
        ArrayList<DirectedGraphNode> res = new ArrayList<>();
        Map<DirectedGraphNode, Integer> nodesIndegree = getNodesIndegree(graph);
        for (DirectedGraphNode node : nodesIndegree.keySet()) {
            if (nodesIndegree.get(node) == 0) {
                dfs(node, nodesIndegree, res);
            }
        }

        return res;
    }

    private void dfs(DirectedGraphNode node, Map<DirectedGraphNode, Integer> nodesIndegree, ArrayList<DirectedGraphNode> res) {
        res.add(node);
        nodesIndegree.put(node, nodesIndegree.get(node) - 1);

        for (DirectedGraphNode neighbor : node.neighbors) {
            nodesIndegree.put(neighbor, nodesIndegree.get(neighbor) - 1);
            if (nodesIndegree.get(neighbor) == 0) {
                dfs(neighbor, nodesIndegree, res);
            }
        }
    }

    //统计每个节点的入度
    private Map<DirectedGraphNode, Integer> getNodesIndegree(ArrayList<DirectedGraphNode> graph) {
        Map<DirectedGraphNode, Integer> map = new HashMap<>();
        for (DirectedGraphNode node : graph) {
            map.put(node, 0);
        }

        for (DirectedGraphNode node : graph) {
            for (DirectedGraphNode neighbor : node.neighbors) {
                map.put(neighbor, map.get(neighbor) + 1);
            }
        }
        return map;
    }
}
